\documentclass[13pt]{beamer}
%\usetheme{Berlin}
\usetheme{Berkeley}
%\usetheme{Warsaw}

%\usepackage[polish]{babel}
%\usepackage[cp1250]{inputenc}
%\usepackage[latin2]{inputenc}

\usepackage{tikz}

\usepackage{polski}
\usepackage[T1]{fontenc}
%\usepackage[cp1250]{inputenc}

%\usepackage[T4]{fontenc} 
\usepackage[polish]{babel}
%\usepackage[cp1250]{inputenc}

\usepackage[utf8x]{inputenc}

%\usepackage[utf8x]{inputenc}
%\usepackage{polski}
%\usepackage[T1]{fontenc}

%\usepackage{default}
\title[Zastosowanie programowania ewolucyjnego do rozwiązywania klasy problemów NP-zupełnych\hspace{2em}\insertframenumber/
\inserttotalframenumber]{Zastosowanie programowania ewolucyjnego do rozwiązywania klasy problemów NP-zupełnych}
%\title{Zastosowanie programowania ewolucyjnego do rozwiązywania klasy problemów NP-zupełnych}
\author{Łukasz Szybka}
\date{\today}
\begin{document}

%\onehalfspacing
\linespread{1.2}
%\baselineskip{16}
%\renewcommand\baselinestretch{1.5}



\frame{\titlepage}

\section{Spis}
\frame{\tableofcontents}

\section{Wstęp - przypomnienie}

\frame
{
  \frametitle{Schemat blokowy algorytmu genetycznego}
	\begin{figure}
          \scalebox{0.38}
	  {
	    \input{../Schemat_blokowy_algorytmu_genetycznego}
	  }
	\end{figure}
}

\frame
{
  \frametitle{Opis problemu komiwojażera}
  Problem polega na znalezieniu najkrótszej drogi między podanymi miastami.
  Droga zaczyna się z ustalonego miasta i kończy w miejscu startu.
  Ilość możliwych dróg równa jest ilości permutacji podzielonej przez 2 (trasę można przebyć w dwóch kierunkach).
  Dla liczby miast n=20 ilość możliwych dróg wynosi $\frac{(n-1)!}{2}=\frac{19!}{2}=60822550204416000$
}

\frame
{
  \frametitle{Reprezentacja w chromosomie}
  Chromosom zawierający ciąg liczb całkowitych od 0 do n-1. Liczby się nie powtarzają
  \begin{table}
    %\caption{Przykładowy chromosom dla problemu komiwojażera}
    %\label{tb:example_chromosome_salesman}
    \begin{center}
	\begin{tabular}{ | l | l |l |l |l |l |l |l |l |}
	\hline
	1&5&8&3&0&2&6&4&7\\ \hline
	\end{tabular}
    \end{center}
  \end{table}
}

\frame
{
  \frametitle{Krzyżowanie}
  Zwykłe krzyżowanie prowadziłoby do utworzenia nieprawidłowych chromosomów.
  Należy zastosować wyspecjalizowane krzyżowanie które tworzy tylko prawidłowe chromosomy.

  \begin{table}
    %\caption{Przykładowy chromosom dla problemu komiwojażera}
    %\label{tb:example_chromosome_salesman}
    \begin{center}
	\begin{tabular}{ | l | l | l|}
	\hline
	chromosom1 & chromosom2\\ \hline
	1 5 8 3 0|2 6 4 7 & 3 5 1 6 0|8 7 2 4\\ \hline
	1 5 {\color{red}2} 3 0|{\color{red}8} 6 4 7 & 3 5 1 6 0|{\color{red}2} 7 {\color{red}8} 4\\ \hline
	1 5 2 3 0|8 {\color{red}7} 4 {\color{red}6} & 3 5 1 {\color{red}7} 0|2 {\color{red}6} 8 4\\ \hline
	1 5 {\color{red}4} 3 0|8 7 {\color{red}2} 6 & 3 5 1 7 0|2 6 {\color{red}4} {\color{red}8}\\ \hline
	1 5 {\color{red}6} 3 0|8 7 2 {\color{red}4} & 3 5 1 {\color{red}8} 0|2 6 4 {\color{red}7}\\ \hline
	\end{tabular}
    \end{center}
  \end{table}

}

\frame
{
  \frametitle{Mutacja}
  Mutacja zamienia miejscami dwa losowe miasta.

  \begin{table}
    %\caption{Przykładowy chromosom dla problemu komiwojażera}
    %\label{tb:example_chromosome_salesman}
    \begin{center}
	\begin{tabular}{|l | l | l |l |l |l |l |l |l |l |}
	\hline
	przed mutacją &1&5&8&3&0&2&6&4&7\\ \hline
	po mutacji    &1&5&{\color{red}2}&3&0&{\color{red}8}&6&4&7\\ \hline
	\end{tabular}
    \end{center}
  \end{table}
}

\section{Klasy}

\frame
{
  \frametitle{Chromosome}
    \begin{figure}
      \includegraphics[height=7cm]{../class_diagram_chromosome.png}
      \label{fig:class_diagram_chromosome}
    \end{figure}
}

\frame
{
  \frametitle{Chromosome factory}
    \begin{figure}
      \includegraphics[width=10cm]{../class_diagram_chromosome_factory.png}
      \label{fig:class_diagram_chromosome_factory}
    \end{figure}
}

\frame
{
  \frametitle{Generation}
    \begin{figure}
      \includegraphics[width=10cm]{../class_diagram_generation.png}
      \label{fig:class_diagram_generation}
    \end{figure}
}

\frame
{
  \frametitle{Environment}
    \begin{figure}
      \includegraphics[height=7cm]{../class_diagram_environment.png}
      \label{fig:class_diagram_environment}
    \end{figure}
}

\frame
{
  \frametitle{Selection strategy}
    \begin{figure}
      \includegraphics[width=10cm]{../class_diagram_selection.png}
      \label{fig:class_diagram_selection}
    \end{figure}
}

\frame
{
  \frametitle{Komiwojażer}
    \begin{figure}
      \includegraphics[width=10cm]{../class_diagram_salesman.png}
      \label{fig:class_diagram_salesman}
    \end{figure}
}

%TODO wzorce projektowe, reprezentacja w chromosomie

\frame
{
  \frametitle{Diagram klas}
	\begin{figure}
	  %\centering
	  \includegraphics[width=9cm]{../class_diagram.png}
	  %\caption{Diagram klas}
	  \label{fig:class_diagram}
	\end{figure}
}


\end{document}
